package codewars.arrays;

import java.util.*;

/**
 * The Supermarket Queue
 * CodeWars: https://www.codewars.com/kata/the-supermarket-queue/train/java
 * Topics: fundamentals, arrays, loops, control flow
 *
 * 类似于限流算法。
 *
 * Created by yzy on 2019-05-07 17:46
 */
public class TheSupermarketQueue {

    public static void main(String[] args) {
        int[] arr = new int[]{6,1,6,1,7,7,6,3};
        int n = 2;
        System.out.println(solveSuperMarketQueue(arr, n));
    }

    /**
     * 在codewars 上看到的解法，思路一样，更优雅
     * @param customers
     * @param n
     * @return
     */
    public static int solveSuperMarketQueue_optimize(int[] customers, int n) {
        int[] result = new int[n];
        for(int i=0; i<customers.length; i++){
            result[0] += result[0] + customers[i];
            Arrays.sort(result);
        }
        return result[n-1];
    }

    public static int solveSuperMarketQueue(int[] customers, int n) {
        // 记录空位的index位置
        Set<Integer> spaceSet = new HashSet<>();
        for(int i=0; i<n; i++){
            spaceSet.add(i);
        }

        int[] lines = new int[n];
        int min = Integer.MAX_VALUE;
        int index = 0;
        int times = 0;
        while(index<customers.length){
            if(!spaceSet.isEmpty()){                        // 如果有空位
                int val = customers[index++];               // 取出当前值，并且index++
                min = val < min ? val : min;                // 更新min值
                Integer space = spaceSet.iterator().next(); // 那取出空位index
                lines[space] = val;                         // val放入空位index中
                spaceSet.remove(space);                     // set中移除空位数据
            }else{
                int tmp = min;    // 需要一个临时变量来记录上一个min值
                min = Integer.MAX_VALUE;
                for(int i=0; i<lines.length; i++){
                    int currVal = lines[i] - tmp;
                    lines[i] = currVal;
                    if(currVal == 0){
                        spaceSet.add(i);                        // 为0，说明位置空出
                    }else{
                        min = currVal < min ? currVal : min;    // 不为0，则更新min值
                    }
                }
                times +=tmp;                                    // times增加min步
            }
        }
        Arrays.sort(lines);
        times += lines[lines.length-1];
        return times;
    }
}
